n=1000;
m=1;
road=[|145,694,9490|
246,666,127|
504,549,4214|
126,4,467|
716,398,5147|
843,268,2822|
965,737,1708|
125,772,6994|
301,419,8311|
464,295,9163|
16,375,6624|
542,161,7667|
603,907,6716|
75,262,1475|
736,601,1078|
67,149,5913|
347,415,4765|
519,728,6596|
803,88,2116|
267,327,9626|
847,243,9729|
731,843,1939|
854,190,542|
356,518,811|
612,80,4731|
538,785,3891|
687,998,4794|
886,299,6945|
748,258,6642|
568,278,1307|
236,791,4493|
397,383,2448|
909,606,584|
87,777,1072|
966,554,5755|
907,895,1143|
188,804,2248|
803,110,2534|
741,872,5947|
873,191,439|
730,939,515|
154,704,2258|
669,358,9119|
613,45,1549|
918,936,5371|
921,285,6442|
845,551,9439|
394,491,8902|
378,294,7017|
21,471,4786|
836,47,5933|
793,642,7746|
677,117,244|
714,272,4111|
613,560,9761|
211,437,8614|
567,770,1882|
507,442,1911|
642,634,3166|
178,163,3607|
541,70,7430|
556,237,846|
761,934,8634|
71,951,2970|
193,332,1163|
359,53,9034|
235,435,9930|
317,253,4740|
734,603,1726|
344,586,2399|
291,460,930|
749,900,6921|
38,449,7076|
759,200,434|
818,49,8616|
509,474,2672|
542,971,5331|
919,502,4969|
293,334,5616|
786,632,766|
170,679,4110|
349,287,6936|
918,143,240|
977,554,8435|
153,976,1196|
605,710,8789|
297,572,3933|
322,345,7482|
953,234,671|
300,820,476|
169,806,5451|
745,282,9046|
981,727,796|
284,774,1834|
723,968,5744|
986,636,6236|
888,73,2244|
434,821,669|
856,96,8737|
244,577,6497|
610,97,1933|
257,406,7185|
387,526,2306|
884,959,4282|
183,584,1078|
626,522,2924|
203,107,5353|
883,716,2220|
364,366,1198|
428,340,8242|
282,172,6203|
330,437,7995|
695,357,1756|
314,30,992|
553,59,6220|
466,812,7341|
731,121,223|
143,259,5268|
942,288,6882|
544,414,424|
555,111,6849|
239,61,5834|
31,832,65|
444,228,1615|
106,827,7416|
607,823,7215|
572,311,4239|
959,460,2488|
665,142,7143|
51,192,2441|
659,301,7953|
466,559,3352|
903,257,2292|
852,471,7069|
178,735,787|
305,345,9892|
953,169,9445|
679,296,6382|
21,848,9507|
838,945,9489|
697,556,9054|
438,341,4611|
948,397,2382|
958,445,1811|
760,495,5540|
177,263,1045|
398,362,2161|
146,787,1121|
661,887,9836|
268,682,1964|
519,536,6143|
24,933,9502|
107,395,2315|
156,532,2217|
54,809,8192|
199,222,2496|
727,816,66|
155,294,7165|
292,169,481|
787,819,8253|
59,919,2387|
629,489,5598|
298,536,7754|
595,685,1080|
616,617,3797|
591,588,8641|
533,707,6078|
813,962,1185|
988,626,7187|
270,955,208|
293,206,9623|
761,372,1951|
497,46,7825|
450,171,4382|
444,512,3387|
418,328,4852|
182,176,1236|
162,184,6658|
898,403,190|
944,739,829|
364,880,1281|
360,717,8300|
487,718,6422|
934,306,1079|
842,353,5853|
346,850,911|
924,692,1832|
452,945,8219|
894,831,5710|
828,589,3812|
739,684,8792|
541,509,7482|
585,129,9223|
847,226,1197|
748,448,5612|
511,601,4384|
836,98,7695|
162,92,8558|
110,467,9897|
254,12,4114|
705,401,858|
303,911,7038|
395,718,1219|
559,788,789|
628,490,3325|
584,925,7729|
710,412,400|
908,155,6478|
100,596,8077|
846,546,8749|
444,505,5013|
166,805,3938|
416,592,2911|
865,847,7974|
986,755,5382|
616,15,4950|
317,779,4936|
421,68,702|
941,893,1225|
865,571,2734|
769,34,4318|
912,122,7333|
198,195,6338|
919,958,1297|
578,533,3237|
529,459,484|
266,1,888|
860,337,8098|
882,872,782|
6,410,7876|
775,411,367|
624,855,4087|
249,764,1642|
549,612,1947|
937,770,3657|
713,277,7125|
785,449,7618|
13,978,1246|
902,969,6431|
926,641,1393|
446,587,3663|
884,334,4993|
62,101,5109|
499,664,2640|
707,606,9558|
383,14,2233|
504,494,5775|
175,15,3623|
885,11,9869|
682,672,3692|
534,194,1139|
218,615,747|
864,479,8696|
423,764,670|
201,998,7925|
334,547,3520|
550,800,9259|
443,680,9924|
43,854,1996|
19,279,2461|
391,582,1677|
964,655,3252|
403,463,6875|
24,3,4085|
270,924,5058|
974,705,7842|
57,685,619|
181,923,6606|
308,152,5472|
678,131,375|
530,53,8886|
886,379,986|
576,569,4522|
278,286,8333|
386,492,5181|
270,709,6104|
640,816,1233|
457,768,4901|
363,210,1553|
714,648,9393|
560,55,354|
644,410,222|
553,565,2758|
363,479,3376|
834,818,8010|
179,116,3184|
75,132,1970|
61,238,6217|
875,916,8411|
10,949,229|
358,455,937|
630,372,353|
982,733,1234|
35,635,332|
652,133,2401|
953,318,356|
144,503,7828|
903,130,3953|
58,633,1199|
32,651,5008|
248,548,4359|
652,16,3330|
509,188,8951|
581,726,1171|
530,876,422|
532,756,1843|
16,331,4591|
381,266,9224|
205,51,9488|
955,799,1689|
215,8,9308|
119,309,1429|
313,305,4337|
552,367,8506|
985,306,620|
199,767,9983|
77,409,9046|
315,930,5995|
593,841,6007|
733,820,201|
133,467,4580|
227,750,4879|
587,784,7951|
95,682,9373|
609,851,3200|
780,948,1181|
127,490,9520|
271,803,8956|
646,230,5663|
182,17,2410|
544,475,1311|
590,382,4267|
552,517,9991|
976,257,2377|
214,454,5041|
382,384,4689|
935,14,7547|
36,740,162|
850,9,4522|
846,281,7585|
769,408,2370|
570,575,2775|
216,729,3807|
789,308,5505|
890,901,3472|
56,592,1487|
256,74,2695|
753,597,3574|
728,603,26|
977,952,427|
298,223,4869|
533,329,7637|
889,994,6117|
680,975,2698|
28,96,8750|
269,462,783|
79,926,5047|
858,231,6856|
195,150,1241|
894,870,6005|
90,980,3203|
124,808,721|
873,969,7689|
261,286,6447|
794,57,3488|
1,172,2554|
918,657,8211|
159,994,1512|
451,959,2897|
51,157,8185|
599,303,9613|
426,200,9603|
148,556,5693|
157,765,2926|
46,255,7116|
424,271,4502|
245,319,9288|
751,178,2989|
984,93,1557|
583,480,985|
938,189,4968|
479,241,2460|
991,412,4140|
132,993,7657|
707,536,8736|
424,920,8863|
853,113,2630|
5,980,1442|
702,453,5126|
637,420,427|
392,939,7738|
808,773,8631|
567,468,6224|
450,840,8949|
392,928,3339|
375,960,5500|
683,148,90|
961,920,18|
950,738,3359|
323,2,3704|
258,203,2593|
809,921,3322|
856,752,3002|
589,66,2878|
719,922,2402|
690,565,214|
488,279,2178|
914,763,77|
179,758,5674|
801,221,1492|
330,252,1030|
569,308,9648|
749,706,1112|
232,1000,4770|
325,745,3116|
735,962,2757|
621,38,851|
459,817,908|
151,696,2536|
59,411,199|
691,337,9151|
205,987,247|
705,557,362|
512,681,185|
219,703,4902|
332,843,4745|
196,136,5798|
384,966,5186|
294,482,9565|
161,42,8822|
580,770,3363|
330,658,9681|
55,792,2409|
667,506,5748|
435,893,8384|
475,205,4755|
253,32,1791|
710,632,1511|
653,113,4641|
695,261,5644|
40,209,6516|
878,117,1764|
100,109,3547|
355,325,111|
915,806,1902|
784,344,199|
315,77,7637|
676,307,1227|
139,481,6288|
139,268,7314|
402,585,530|
86,486,956|
146,440,9185|
13,436,5676|
157,239,272|
795,538,6853|
781,790,51|
244,394,401|
557,541,6123|
649,964,8513|
150,433,6209|
999,25,7218|
24,758,7585|
810,638,8739|
950,156,6986|
82,765,1302|
91,723,9710|
94,513,5600|
431,899,4981|
967,263,9480|
70,90,7513|
163,168,2732|
350,548,7399|
8,792,3981|
324,124,4452|
140,417,1196|
349,29,8902|
802,309,1385|
782,346,2279|
61,393,8841|
991,891,6230|
99,279,795|
776,501,9557|
11,944,6580|
473,590,940|
302,677,8715|
911,226,4900|
406,389,5570|
121,712,9309|
759,724,9947|
938,858,2856|
357,840,3897|
992,165,8910|
20,797,7574|
626,498,1671|
951,217,8350|
184,757,7572|
421,105,9218|
230,114,806|
667,311,4710|
619,295,3220|
983,591,2883|
753,554,3737|
34,916,7526|
91,896,516|
692,327,1087|
332,164,1318|
798,298,1347|
840,472,9879|
287,746,188|
454,476,1938|
1000,48,203|
906,135,5444|
64,611,1081|
567,41,8033|
137,949,6775|
543,920,8175|
267,22,482|
424,236,2969|
304,932,1704|
968,821,1869|
701,347,955|
807,514,1519|
768,500,2458|
221,439,1556|
400,366,94|
104,252,7623|
431,700,2466|
527,815,1639|
391,374,2439|
234,956,1031|
861,102,373|
242,26,269|
62,70,135|
493,395,8019|
434,458,7496|
841,601,1449|
909,970,5210|
689,845,9793|
352,720,8480|
793,112,2178|
223,594,3748|
745,315,2262|
817,797,1190|
477,466,3228|
71,982,440|
992,88,1606|
354,321,8706|
584,799,5724|
510,643,606|
566,12,5191|
401,744,941|
791,989,8279|
874,665,3424|
351,377,5182|
754,730,9844|
224,510,675|
779,763,4378|
440,106,1215|
898,506,4847|
565,216,4771|
174,164,6676|
835,9,7856|
644,385,5725|
249,340,5422|
777,372,966|
307,839,930|
995,546,9300|
808,312,5032|
870,780,3758|
649,232,4773|
313,772,7798|
300,273,693|
575,318,7063|
118,666,8019|
798,370,6811|
595,990,3469|
644,693,6676|
598,882,2405|
673,699,5383|
906,830,9298|
275,555,3995|
571,762,9039|
897,413,7807|
291,176,1176|
218,421,7569|
94,221,5783|
339,112,313|
515,476,1979|
973,77,6714|
483,89,4449|
27,507,1269|
12,971,984|
508,399,4811|
620,75,4227|
418,999,241|
520,453,1178|
743,909,9033|
609,561,1906|
36,860,3992|
826,671,6847|
101,681,7034|
469,698,1064|
623,899,830|
550,747,538|
299,376,2707|
7,571,9449|
28,417,650|
3,622,7286|
634,462,7912|
305,62,1484|
501,650,5157|
359,839,7249|
581,85,8862|
655,406,1103|
957,617,3663|
180,43,5430|
478,405,6154|
117,281,6392|
439,543,7587|
82,150,7532|
902,543,8258|
708,867,5740|
195,328,8261|
931,185,6806|
880,495,693|
711,368,8559|
563,11,9657|
65,458,889|
756,611,8392|
127,471,3751|
580,946,3637|
415,105,8143|
499,407,5216|
457,886,4888|
978,885,5582|
771,796,9783|
693,155,3624|
225,310,4088|
115,399,1529|
954,81,8569|
228,686,8468|
908,404,7260|
804,778,1137|
621,142,6232|
938,844,7065|
392,528,6152|
698,633,2361|
231,927,2123|
755,725,2877|
357,676,1714|
608,795,4712|
972,967,8454|
965,274,1140|
262,452,1679|
118,905,7005|
633,639,589|
504,388,913|
187,981,1091|
251,488,9660|
193,79,8584|
47,326,9792|
341,666,20|
41,525,8476|
715,700,3625|
689,335,5839|
433,484,5975|
197,656,4528|
408,627,940|
739,470,8294|
829,646,4816|
310,336,8606|
928,71,94|
34,979,1289|
283,939,9093|
828,689,8603|
491,44,8185|
926,869,6957|
320,823,6251|
312,68,964|
655,212,7145|
102,579,808|
766,60,2054|
80,588,4390|
276,956,5865|
170,560,3710|
605,338,416|
732,174,4974|
154,467,1758|
648,972,7205|
545,932,9361|
922,912,1064|
306,614,917|
760,233,4353|
54,50,241|
813,622,979|
658,964,827|
28,192,9079|
658,862,547|
930,916,138|
503,708,7181|
766,213,8717|
617,84,8225|
622,99,9084|
158,86,8825|
701,213,199|
379,456,3575|
794,234,6404|
662,894,6179|
639,81,5131|
569,761,7110|
427,201,9992|
743,102,8096|
902,668,124|
272,240,5698|
867,688,381|
821,695,5477|
950,535,8098|
480,101,3809|
518,997,9640|
335,857,219|
333,914,955|
600,863,4424|
737,345,4110|
83,744,9851|
703,242,3259|
759,822,9755|
15,537,3747|
780,282,704|
814,712,2472|
38,346,4928|
325,416,8190|
3,971,5342|
607,310,4125|
557,683,767|
967,35,2322|
879,128,6519|
292,250,604|
521,742,6354|
604,297,902|
52,751,9509|
552,660,371|
787,535,8842|
775,796,9405|
374,525,687|
947,37,8362|
810,824,5656|
612,930,8461|
8,47,7530|
164,374,9886|
301,753,1220|
516,802,3067|
578,454,9657|
124,33,275|
830,250,231|
857,616,9036|
361,446,7858|
912,621,7629|
793,243,6276|
245,342,1893|
123,702,7579|
120,72,3554|
899,153,7802|
671,120,618|
810,981,8327|
977,107,8534|
179,928,5998|
212,670,1266|
41,226,6157|
411,763,7310|
775,162,4023|
429,490,640|
23,949,9297|
425,832,8224|
172,323,936|
219,915,6139|
929,714,6856|
419,852,7520|
182,194,9462|
69,650,1242|
238,496,376|
741,141,5796|
562,17,935|
512,465,8263|
342,765,4164|
618,89,608|
725,378,6896|
210,535,4259|
722,204,114|
650,924,5001|
380,286,4598|
526,656,3423|
246,839,312|
637,671,9733|
605,469,4205|
216,260,2256|
545,85,5434|
672,156,1176|
530,573,9834|
243,469,2506|
18,910,5341|
870,963,47|
767,837,5940|
721,904,7556|
773,78,1126|
750,460,5448|
539,713,1678|
478,647,803|
284,74,9674|
371,393,6080|
631,511,2766|
952,447,648|
656,138,1551|
262,259,6818|
897,876,9000|
103,725,9932|
618,922,6888|
295,501,7397|
76,651,7490|
747,983,57|
405,455,508|
614,720,2782|
139,645,776|
653,215,7634|
722,468,2959|
291,524,331|
133,255,2425|
643,185,3342|
917,339,9605|
280,432,4051|
855,493,80|
733,717,8108|
614,486,2422|
408,365,5242|
859,497,9578|
18,69,3713|
489,697,632|
484,984,7322|
851,484,7661|
878,123,2593|
220,514,1077|
638,576,1448|
370,354,1176|
72,136,8003|
746,968,9471|
815,144,6906|
904,955,9377|
576,852,1082|
833,570,5365|
480,693,7236|
587,952,4892|
521,961,12|
731,131,2926|
558,779,332|
143,115,4580|
109,240,7535|
452,844,6638|
57,888,4006|
797,343,62|
10,625,9526|
578,669,2906|
186,534,8407|
834,598,6846|
996,879,2775|
767,782,6695|
430,58,5429|
413,997,7881|
108,673,9350|
669,206,4954|
794,412,436|
485,439,69|
159,140,1850|
872,523,9545|
359,607,2985|
574,443,6999|
588,553,1927|
529,881,6136|
391,30,4410|
68,735,3252|
53,799,1825|
367,423,1659|
263,316,300|
620,663,5696|
826,978,3791|
241,67,2201|
563,229,1130|
290,276,6785|
105,337,3236|
327,726,8822|
240,265,8868|
662,373,60|
378,915,102|
385,441,6455|
600,874,1652|
674,668,9493|
982,723,4106|
91,368,1106|
589,646,3145|
774,738,8321|
507,783,1941|
921,532,176|
311,813,8679|
863,913,2727|
82,941,6620|
208,828,7142|
934,792,830|
46,706,170|
449,564,8068|
111,405,6378|
945,996,7812|
409,540,9984|
944,363,4353|
593,348,3178|
946,160,9660|
154,514,2909|
134,44,2346|
610,13,3917|
165,425,4818|
969,858,8855|
643,726,1088|
173,664,224|
709,849,8842|
844,503,8066|
250,264,6256|
679,602,1374|
407,236,5914|
350,510,1029|
746,531,391|
203,782,2309|
781,470,4854|
842,963,3027|
814,892,2669|
750,39,491|
755,209,467|
329,180,7761|
609,914,217|
1000,516,1276|
201,255,55|
289,144,85|
972,417,6794|
675,251,1317|
398,410,9990|
227,878,7988|
940,518,4314|
353,871,5699|
461,850,2726|
498,684,6707|
188,202,1454|
694,600,1019|
426,415,2235|
606,396,7510|
801,654,4138|
134,95,6962|
351,635,7818|
37,989,3442|
942,703,9106|
659,825,4317|
153,845,1369|
672,137,1630|
814,923,3820|
167,783,9602|
227,975,9980|
866,652,3053|
583,880,3598|
548,811,6853|
422,697,4153|
328,585,5284|
259,649,5483|
277,451,6779|
851,459,9716|
868,497,7050|
826,998,5449|
887,836,249|
335,350,370|
734,369,248|
812,210,9180|
151,976,340|
63,801,5209|
805,624,2865|
698,147,9467|
570,890,9281|
126,137,2077|
525,511,2861|
336,207,5226|
347,598,5157|
427,247,6979|
108,983,1835|
423,419,9837|
432,215,1814|
948,683,285|
277,390,1536|
338,943,1739|
151,877,4104|
783,615,2347|
299,433,9584|
837,492,1255|
648,519,3583|
709,526,39|
677,142,7425|];